package P1线性结构;

import java.util.Iterator;

//底层由数组实现的一个双端队列
public class ArrayDeque<E> implements Deque<E>, Stack<E>, Queue<E>, Iterable<E> {
    private static int DEFAULT_CAPACITY = 10;   //最小默认容量
    private E[] data;   //存储元素的容器
    private int size;   //元素的有效个数
    private int front;  //表头的指针
    private int rear;   //表尾的指针

    public ArrayDeque() {
        //最小默认容量为10 => 最多存储10个元素 但是记住一点 rear是一直指向一个空空间的
        //所以会留出一个位置 => +1 将这个预留的空间额外补充
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public void addFirst(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element can not be null");
        }
        //判断是否需要扩容
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        front = (front - 1 + data.length) % data.length;
        data[front] = element;
        size++;
    }

    @Override
    public void addLast(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element can not be null");
        }
        //判断是否需要扩容
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E removeFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("deque is empty");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        //判断是否需要缩容
        if (size == (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E removeLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("deque is empty");
        }
        rear = (rear - 1 + data.length) % data.length;
        E ret = data[rear];
        //实际上 元素没有被删除 只不过把该元素看做在有效区间[front,rear)之外
        size--;
        //判断是否需要缩容
        if (size == (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    //扩容/缩容操作
    private void resize(int newLength) {
        E[] newData = (E[]) new Object[newLength];
        int index = 0;  //遍历newData
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        front = 0;
        rear = index;
        data = newData;
    }

    @Override
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("deque is empty");
        }
        return data[front];
    }

    @Override
    public E getLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("deque is empty");
        }
        return data[(rear - 1 + data.length) % data.length];
    }


    @Override
    public int size() {
        return size;
        //return (rear - front + data.length) % data.length
        //也可以通过front 与 rear来进行计算
        //如果front < rear    rear - front
        //如果rear < front    n - (front - rear)
        /*

        #     # #
        0 1 2 3 4
          r   f
        (1 - 3 + 5) % 5

          # # #
        0 1 2 3 4
          f     r
        统一公式：(r - f + n) % n
        */
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && front == rear;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        size = 0;
        front = 0;
        rear = 0;
    }

    //队列的操作
    @Override
    public void offer(E element) {
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }

    //栈的操作
    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return removeLast();
    }

    @Override
    public E peek() {
        return getLast();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
        } else {
            for (int i = front; i != rear; i = (i + 1) % data.length) {
                sb.append(data[i]);
                if ((i + 1) % data.length == rear) {
                    sb.append(']');
                } else {
                    sb.append(',');
                    sb.append(' ');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object obj) {
        /*
        1.是否是null
        2.是否是自己
        3.是否同类型
        4.是否元素个数一样
        5.是否元素按照顺序相同
        */
        if (obj == null) {
            return false;   //和null比 肯定不相等
        }
        if (obj == this) {
            return true;    //和自己比 肯定相等
        }
        if (obj instanceof ArrayDeque) {
            ArrayDeque<E> other = (ArrayDeque<E>) obj;
            if (this.size == other.size) {
                E[] v1 = this.data;
                E[] v2 = other.data;
                int p1 = this.front;
                int p2 = other.front;
                while (p1 != this.rear) {
                    if (!v1[p1].equals(v2[p2])) {
                        return false;   //元素个数一样 但是由不一样的元素
                    }
                    p1 = (p1 + 1) % data.length;
                    p2 = (p2 + 1) % data.length;
                }
                return true;    //元素个数一样 而且都相等
            }
        }
        return false;   //不是同类型 元素个数不一样
    }


    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    private class ArrayDequeIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}
